1. Field of the Invention
The present invention relates to a multiplying circuit, and in particular, to a multiplying circuit suitable for an integrated circuit.
2. Description of the Prior Art
A multiplying circuit which forms partial products, adds them, and obtains the multiplication result is known. This multiplying circuit is mostly occupied by a circuit portion which adds partial products. To reduce the circuit scale of the multiplying circuit, by using the booth's algorithm, the number of partial products is decreased.
FIGS. 1 and 2 show the conception of multiplication using additions of partial products. In this multiplication, a rounding process shown in FIG. 1 and a complement calculating process shown in FIG. 2 are performed.
First, with reference to FIG. 1, the additions of partial products will be described. In FIG. 1, the conception of multiplication in accordance with the secondary Booth's algorithm is shown.
In FIG. 1, in each of partial products PP1 to PP4, bits BP0 to BP7 represent a multiplicand of eight bits. In addition, a bit BP8 represents a start bit Si (where i=1 to 4, Si=-2.sup.n-1) having a negative weight. The bit BP7 represents the digit of (2.sup.n-1). The bit BPCC represents the position of bit "1" which is added when data is converted into the notation using the complement of 2. In other words, according to the secondary Booth's algorithm, a partial product can be a value which is multiplied by 0, (.+-.1), or (.+-.2). In this specification, as the notation representing the collection of these values, the partial products PP1 to PP4 shown in FIG. 1 are used.
In FIG. 1, in the partial product PP2, the position of the bit BP0 which is the LSB is moved by two bits in the MSB direction on the basis of the position of the bit BP0 of the partial product PP1. Likewise, in the partial products PP3 and PP4, the position of the bit BP0 which is the LSB is moved by two bits in the MSB direction.
By adding the above-mentioned partial products PP1 to PP4, a product PROD shown in FIG. 1 is formed. The product PROD is not output entirely, but only partially due to a restriction of hardware. In the example, as shown in FIG. 1, digits on the L side of an alternate long and short dash line LCH are addition data which are output in accordance with an output word length. The remaining digits which are on the R side of the alternate long and short dash line LCH are addition data which are not output.
Next, with reference to FIG. 1, a rounding process will be described. The rounding process is used to output a part of calculation result due to various reasons. In this example as shown in FIG. 1, a rounding bit BPRU is added to low order digits of the alternate long and short dash line LCH which defines the output word length so as to obtain a product PROD. In addition, the remaining data on the right (arrow R side) of the alternate long and short dash line LCH is discarded. Such a process which determines data according to the output word length is the rounding process.
Next, with reference to FIG. 2, a calculating process of the complement of 2 will be described. The complement calculating process is performed to eliminate the necessity of processing the MSBs (=-2.sup.n-1) of the partial products PP1 to PP4 represented with a solid line LO shown in FIG. 2.
In FIG. 2, the start bit Si can be serially disposed as follows. EQU -[(0) (S4) (0) (S3) (0) (S2) (0) (S1)]
When the polarities of all the bits are inverted, the resultant bits are represented as follows. Hereunder, "*" represents the state where the polarity was inverted. EQU [(1) (S4*) (1) (S3*) (1) (S2*) (1) (S1*)]
By adding a complement processing bit BPC (="1") to the LSB, the calculating process of the complement of 2 is performed. Thus, without necessity of processing MSBs (=-2.sup.n-1) of the partial products PP1 to PP4, the product PROD as the multiplication result can be obtained by simply adding the partial products PP1 to PP4.
FIG. 3 shows an example of a multiplying circuit which performs a multiplication in accordance with the above-mentioned secondary Booth's algorithm. The multiplying circuit shown in FIG. 3 will now be described.
In the construction of FIG. 3, a multiplier of m bits (where m=8 in this example) is stored in a register 205. In addition, a multiplicand of n bits is stored in a register 206.
In the register 205, the multiplier is divided into blocks of two bits. One high order bit of a low order block is added to one low order bit of a high order block. Thus, data of successive three bits is formed. This data of three bits is supplied to each of Booth's encoder modules (hereinafter referred to as the BEMs) 208 to 211. In a register 212, data (="0") is stored. This data is supplied to the BEM 208.
Data of two bits, b1 and b2, on the LSB side of the multiplier is supplied to the BEM 208. In addition, as a bit b0, the data (="0") from the register 212 is supplied to the BEM 208. Further, the high order bit b2 of bits b1 and b2 is supplied to the BEM 209 as the LSB thereof.
Likewise, data of two bits, b3 and b4, is supplied to the BEM 209. The bit b2 is supplied to the BEM 209 as the LSB thereof. The high order bit b4 of bits b3 and b4 is supplied to the BEM 210 as the LSB thereof.
Data of two bits, b5 and b6, is supplied to the BEM 210. The bit b4 is supplied to the BEM 210 as the LSB thereof. The high order bit b6 of the two bits b5 and b6 is supplied to the BEM 211 as the LSB thereof.
Data of two bits, b7 and b8, is supplied to the BEM 211. The bit b6 is supplied to the BEM 211 as the LSB thereof.
In the BEMs 208 to 211, signals which define the magnification and pluse/minus sign of a partial product are formed in accordance with the data of three bits which is supplied in the above-mentioned manner. These signals are supplied from the BEMs 208 to 211 to partial product generating circuits (hereinafter referred to as the PPGs) 215 to 218, respectively.
On the other hand, the multiplicand of n bits which is received from the register 206 is supplied to the PPGs 215 to 218.
In the PPGs 215 to 218, respective partial products PP215 to PP218 where the complement calculating process (sign correcting process) has been performed are formed in accordance with the signals which define the multiplication and plus/minus sign of the partial products.
In each of the partial products PP215 to PP218, two bits of [(1) (Si*)], where the complement calculating process has been performed for the start bit Si, and the bit BPCC are added to the multiplicand of n bits. Thus, each of the partial products PP215 to PP218 is represented with (n+3) bits. These partial products PP215 to PP218 are supplied to carry ripple adders (hereinafter referred to as CRAs) 221 to 224, respectively.
An initial value, the above-mentioned BPC bit, and so forth are supplied from an initial value setting circuit 220 to the CRA 221. A part of the initial value is obtained through an output terminal.
In the CRA 221, an addition is performed in accordance with the partial product PP215 which is supplied from the PPG 215 and the initial value, the complement processing bit BPC, and so forth which are supplied from the initial value setting circuit 220. An addition output of the CRA 221 is obtained from an output terminal thereof. In addition, a carry output of the CRA 221 is supplied to the CRA 222, which follows the CRA 221.
In the CRA 222, the partial product PP216 which is supplied from the PPG 216 and the carry output which is supplied from the CRA 221 are added. An addition output of the CRA 222 is obtained from an output terminal thereof. In addition, a carry output of the CRA 222 is supplied to the CRA 223, which follows the CRA 222.
In the CRA 223, the partial product PP217 which is supplied from the PPG 217 and the carry output which is received from the CRA 222 are added. An addition output of the CRA 223 is obtained from an output terminal thereof. In addition, a carry output of the CRA 223 is supplied to the CRA 224, which follows the CRA 223.
In the CRA 224, the partial product PP218 which is supplied from the PPG 218 and the carry output which is received from the CRA 223 are added. An addition output of the CRA 224 is obtained from an output terminal thereof. In addition, a carry output of the CRA 224 is supplied to an output terminal thereof. Thus, the product PROD is obtained.
In the conventional multiplying circuit according to the Booth's algorithm, arrays which perform a rounding process, complement calculating process, and so forth necessary for adding the partial products PP1 to PP4 were irregularly and two-dimensionally disposed as shown in FIG. 2.
In the conventional multiplying circuit according to the Booth's algorithm, the above-mentioned irregularly and two-dimensionally disposed circuit construction was used as it was. In other words, in the layout stage, efforts for constructing the circuit as regularly as possible were made through experience and perception of the designer. However, since the circuit construction was irregular, in the LSI producing stage, the circuit could not be effectively designed by using basic circuits in the same construction.
For example, as shown in FIG. 4, an example where a circuit is hierarchically constructed of multiplying cells as basic circuits, each of which consists of an AND gate 201 and a full adder 202, is known. However, this basic circuit construction was still in a small scale.
In addition, as another example, redundant circuits such as carry adders as shown in FIG. 3 were used as basic circuits. A multiplication was performed by using these basic circuits which were disposed in parallel. However, the carry adders which were used as basic circuits were redundant. Thus, this construction was not suitable from an optimum design point of view.
Although a combination type multiplying circuit can be designed in the above-mentioned manner, so far a time-division type multiplying circuit which performs a multiplication repeatedly using small circuits has not been effectively accomplished.